package exercise49;

/**
 * @Author Fizz Pu
 * @Date 2021/8/11 下午2:27
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，你需要找出一个连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
 *
 * 请你找出符合题意的 最短 子数组，并输出它的长度。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [2,6,4,8,10,9,15]
 * 输出：5
 * 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
 * 示例 2：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：0
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：0
 *  
 *
 * 提示：
 *
 * 1 <= nums.length <= 104
 * -105 <= nums[i] <= 105
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */



public class Lee581 {
    public static void main(String[] args) {

    }

    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int[] ori = Arrays.copyOf(nums, len);
        Arrays.sort(nums);
        int left = 0;
        int right = len - 1;

        // 从前往后寻找第一个不相等的位置
        while (left < len && nums[left] == ori[left]) {
            left++;
        }

        // 找不到，已经有序
        if (left >= len) {
            return 0;
        }

        // 从后往前寻找第一个不相等的位置
        while (right >= 0 && nums[right] == nums[right]) {
            right--;
        }

        return right - left + 1;
    }
}
